МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний Університет "Львівська Політехніка"
Розрахункова робота
з дисципліни:"Теорія алгоритмів"
Варіант 9
Пройдіть в лабіринті від майданчика 1 до майданчика 8: а) так, щоб відвідати всі майданчики по одному разу; б) найкоротшим шляхом.
Програмний код:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Zik
{
public partial class Form1 : Form
{
int endElement = 8;
public List<int>[] list = new List<int>[8];
public List<List<int>> playList = new List<List<int>>();
public List<int> way = new List<int> ();
Point[] poi = new Point[18] { new Point(45, 160), new Point(85, 160),
new Point(96, 149), new Point(96, 76),
new Point(104, 76), new Point(182, 149),
new Point(106, 160), new Point(172, 160),
new Point(192, 160), new Point(250, 160),
new Point(260, 150), new Point(260, 86),
new Point(270, 160), new Point(330, 160),
new Point(270, 76), new Point(342, 150),
new Point(351, 160), new Point(413, 160)};
public Form1()
{
InitializeComponent();
list[0] = new List<int> { 1 };
list[1] = new List<int> { 2 };
list[2] = new List<int> { 4, 3 };
list[3] = new List<int> { 4 };
list[4] = new List<int> { 5 };
list[5] = new List<int> { 7, 6 };
list[6] = new List<int> { 7 };
list[7] = new List<int> { 8 };
}
private void startToolStripMenuItem_Click(object sender, EventArgs e)
{
panel1.Visible = true;
FormStartPicture();
}
public void FormStartPicture()
{
Graphics g = panel1.CreateGraphics();
Pen rp = new Pen(Color.Black, 1);
g.DrawLine(rp, poi[0], poi[1]);
g.DrawLine(rp, poi[2], poi[3]);
g.DrawLine(rp, poi[4], poi[5]);
g.DrawLine(rp, poi[6], poi[7]);
g.DrawLine(rp, poi[8], poi[9]);
g.DrawLine(rp, poi[10], poi[11]);
g.DrawLine(rp, poi[12], poi[13]);
g.DrawLine(rp, poi[14], poi[15]);
g.DrawLine(rp, poi[16], poi[17]);
}
private void порахуватиToolStripMenuItem_Click(object sender, EventArgs e)
{
foreach (int n in list[0])
{
way.Add(n);
if (n != endElement)
{
List<int> way1 = new List<int>();
foreach (int c in way)
{ way1.Add(c); }
Recursive(n, way1);
}
else
{
playList.Add(way);
}
}
MessageBox.Show("Пораховано !!!", "Ahtung", MessageBoxButtons.OK, MessageBoxIcon.Information);
}
private void Recursive(int n, List<int> way)
{
foreach (int i in list[n])
{
if(i != list[n][0]) way.RemoveAt(way.Count-1);
way.Add(i);
if (i != endElement)
{
List<int> way1 = new List<int>();
foreach (int c in way) way1.Add(c);
Recursive(i, way1);
}
else
{
playList.Add(way);
}
}
}
private void вихідToolStripMenuItem_Click(object sender, EventArgs e)
{
Close();
}
private void результатиToolStripMenuItem_Click(object sender, EventArgs e)
{
panel2.Visible = true;
richTextBox1.Text = " Всього шляхів:" + playList.Count + "\n";
for (int i = 0; i < playList.Count; i++)
...
